package com.xjh.basestudy.leetcode.question;

/**
 * @author XuJianHua
 * @version 1.0
 * @company 湖南安第斯信息科技有限公司, 版权所有
 * @date 2022/4/16 14:08
 */

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
/*
 * 输入一个序列，如： 1，2，3，4，2
 * 输入一个整数，如：6
 * 求子序列和为整数的最大长度长度
 * 上述例子和为6的子序列有1，2，3和4，2
 * 最长子序列为1，2，3，长度为3
 * 如果没有和等于6的序列，则返回null
 * */

public class LongestSubsequence {
    public static void main(String[] args) {
        int[] num = {1, 2, 3, 4, 2, 1, 1, 1, 1, 1};
        int sum = 6;
        List<Integer> l = fun(num, sum);
        if (l.size() == 0) {
            System.out.println("NULL");
        } else {
            System.out.println(Collections.max(l));
        }
    }

    public static List<Integer> fun(int[] arr, int sum) {
        //定义一个数组，将每种和为sum的数组元素数量加入
        List<Integer> list = new ArrayList<Integer>();
        //外层for:从第一个（第二个。。。）元素开始往后累加，判断元素之和是否为sum
        for (int i = 0; i < arr.length; i++) {
            int sums = 0;
//            注意j=i，这样才不会从数组的第一个数开始累加
            for (int j = i; j < arr.length; j++) {
                sums += arr[j];
                if (sums == sum) {
                    list.add(j - i + 1);
                    break;
                    //如果超出需要的sum直接终止循环
                } else if (sums > sum) {
                    break;
                } else {
                    continue;
                }
            }
        }
        return list;
    }

    public static List<Integer> funtest(int[] arr, int sum) {
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            int sums = 0;
            for (int j = i; j < arr.length; j++) {
                sums = sums +arr[j];
                if(sums == sum){
                    list.add(j-i+1);
                    break;
                }else if(sums >sum){
                    break;
                }else{
                    continue;
                }
            }
        }

        return list;
    }


}

